UVa/423 - MPI Maelstrom/423.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 #define D(x) cout << #x " is " << x << endl
  22
  23 const int oo = INT_MAX >> 2;
  24 int g[100][100];
  25
  26 int main(){
  27   int n;
  28   scanf("%d", &n);
  29
  30   for (int i=1; i<n; ++i){
  31     for (int j=0, x; j<i; ++j){
  32       char buf[32];
  33       scanf("%30s", buf);
  34       if (!strcmp(buf, "x")){
  35         x = oo;
  36       }else{
  37         x = atoi(buf);
  38       }
  39       g[i][j] = g[j][i] = x;
  40     }
  41     g[i][i] = 0;
  42   }
  43
  44   for (int k=0; k<n; ++k){
  45     for (int i=0; i<n; ++i){
  46       for (int j=0; j<n; ++j){
  47         g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  48       }
  49     }
  50   }
  51
  52   int ans = -1;
  53   for (int j=0; j<n; ++j){
  54     ans = max(ans, g[0][j]);
  55   }
  56
  57   printf("%d\n", ans);
  58   return 0;
  59 }